package __回溯算法

/*
https://leetcode.cn/problems/combination-sum-iii/

216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9, 每个数字 最多使用一次, 返回 所有可能的有效组合的列表 。
该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:
输入: k = 3, n = 7    k:数字个数 n:累加和
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

思路:
例如: k=2, n=4为例, 画树形结构模拟解题过程

					[1,9]取数

	1				2				3				4
	[1] 和1			[2] 和2			[3] 和3			[4] 和4
	[2,9]范围取数字   [3,9]范围取数字   [4,9]范围取数字	[5,9]范围取数字  ...

	[1,2]和3
	[3,9]范围取数字
*/
var (
	res216  [][]int //子结果数组
	path216 []int   //总结果数组
)

func combinationSum3(k int, n int) [][]int {
	res216, path216 = make([][]int, 0), make([]int, 0, 0) //初始化子结果数组, 总结果数组
	dfs216(k, n, 1, 0)                                    //k:个数 n:总和 start:从1开始 (到9结束)  sum:当前累加值
	return res216
}
func dfs216(k, n int, start int, sum int) {
	if len(path216) == k { //终止条件   如果已经达到k长度, 开始判断总和
		if sum == n { //如果累加值 == n, 将当前path添加进结果数组
			tmp := make([]int, k)
			copy(tmp, path216)
			res216 = append(res216, tmp)
		}
		return
	}
	for i := start; i <= 9; i++ { //i从1开始, 到9结束
		if sum+i > n || 9-i+1 < k-len(path216) { //减枝   如果sum+i已经超过n || 剩余节点个数<所需个数
			break
		}
		path216 = append(path216, i)       //当前节点加入path
		dfs216(k, n, i+1, sum+i)           //k,n值不变, i+1向后一个节点, sum+i计算累加值
		path216 = path216[:len(path216)-1] //弹出数组末尾元素
	}
}
